﻿namespace Leetcode.N0417;
public class Solution
{
    public IList<IList<int>> PacificAtlantic(int[][] heights)
    {

        var ans = new List<IList<int>>();
        var queue = new Queue<(int row, int col)>();
        var rowCount = heights.Length;
        var colCount = heights[0].Length;

        var visited = new bool[rowCount * colCount];
        var flags = new bool[rowCount * colCount];

        for (int row = 0; row < rowCount; row++)
        {
            queue.Enqueue((row, colCount - 1));
        }

        for (int col = 0; col < colCount; col++)
        {
            queue.Enqueue((rowCount - 1, col));
        }

        while (queue.Count > 0)
        {
            var list = new List<(int row, int col)>();
            while (queue.Count > 0)
            {
                list.Add(queue.Dequeue());
            }

            foreach (var item in list)
            {
                var index = item.row * colCount + item.col;
                flags[index] = true;
                visited[index] = true;
                this.Enqueue(heights, queue, visited, item);
            }
        }

        visited = new bool[rowCount * colCount];
        queue = new Queue<(int row, int col)>();

        for (int row = 0; row < rowCount; row++)
        {
            queue.Enqueue((row, 0));
        }

        for (int col = 0; col < colCount; col++)
        {
            queue.Enqueue((0, col));
        }

        while (queue.Count > 0)
        {
            var list = new List<(int row, int col)>();
            while (queue.Count > 0)
            {
                list.Add(queue.Dequeue());
            }

            foreach (var item in list)
            {
                var index = item.row * colCount + item.col;
                if (flags[index] && !visited[index])
                {
                    ans.Add(new List<int>() { item.row, item.col });
                }

                visited[index] = true;
                this.Enqueue(heights, queue, visited, item);
            }
        }

        return ans;
    }

    private void Enqueue(int[][] heights, Queue<(int row, int col)> queue, bool[] visisted, (int row, int col) current)
    {
        var pos = new (int row, int col)[]{
            (current.row-1,current.col),(current.row+1,current.col),
            (current.row,current.col-1),(current.row,current.col+1),
            };
        var rowCount = heights.Length;
        var colCount = heights[0].Length;
        foreach (var item in pos)
        {
            if (item.row < 0 || item.row >= rowCount || item.col < 0 || item.col >= colCount)
            {
                continue;
            }

            if (visisted[item.row * colCount + item.col])
            {
                continue;
            }

            if (heights[item.row][item.col] < heights[current.row][current.col])
            {
                continue;
            }
            queue.Enqueue(item);
        }
    }

}